1. Related Invention
IBM application Ser. No. 09/027,765 entitled "Method and Apparatus for a Symmetric Block Cipher using Multiple Stages", filed Feb. 23, 1998.
2. Field of the Invention
The present invention relates to cryptography, and deals more particularly with a system and method for a symmetric key block cipher. This cipher uses multiple stages, where the stages have different structures and different subround functions. The cipher allows the block size, key size, and number of rounds per stage of ciphering to vary.
3. Description of the Related Art
Cryptography is a security mechanism for protecting information from unintended disclosure by transforming the information into a form that is unreadable to humans, and unreadable to machines that are not specially adapted to reversing the transformation back to the original information content. The cryptographic transformation can be performed on data that is to be transmitted electronically, such as an electronic mail message, and is equally useful for data that is to be securely stored, such as the account records for customers of a bank or credit company.
In addition to preventing unintended disclosure, cryptography also provides a mechanism for preventing unauthorized alteration of data transmitted or stored in electronic form. After the data has been transformed cryptographically, an unauthorized person is unlikely to be able to determine how to alter the data, because the specific data portion of interest cannot be recognized. Even if the unauthorized user knew the position of the data portion within a data file or message, this position may have been changed by the transformation, preventing the unauthorized person from merely substituting data in place. If an alteration to the transformed data is made by the unauthorized user despite the foregoing difficulties, the fact of the alteration will be readily detectable, so that the data will be considered untrustworthy and not relied upon. This detection occurs when the transformation is reversed: the encrypted data will not reverse to its original contents properly if it has been altered. The same principle prevents unauthorized addition of characters to the data, and deletion of characters from the data, once it has been transformed.
The transformation process performed on the original data is referred to as "encryption". The process of reversing the transformation, to restore the original data, is referred to as "decryption". The terms "encipher" and "decipher" are also used to describe these processes, respectively. A mechanism that can both encipher and decipher is referred to as a "cipher".
Data encryption systems are well known in the data processing art. In general, such systems operate by performing an encryption operation on a plaintext input block, using an encryption key, to produce a ciphertext output block. "Plaintext" refers to the fact that the data is in plain, unencrypted form. "Ciphertext" indicates that the data is in enciphered, or encrypted, form. The receiver of an encrypted message performs a corresponding decryption operation, using a decryption key, to recover the original plaintext block.
A cipher to be used in a computer system can be implemented in hardware, in software, or in a combination of hardware and software. Hardware chips are available that implement various ciphers. Software algorithms are known in the art as well.
Encryption systems fall into two general categories. Symmetric (or secret key) encryption systems use the same secret key for both encrypting and decrypting messages. An example of a symmetric encryption system is the Data Encryption Standard (DES) system, which is a United States federal standard described in NBS FIPS Pub 46. In the DES system, a key having 56 independently specifiable bits is used to convert 64-bit plaintext blocks to ciphertext blocks, or vice versa.
Asymmetric (or public key) encryption systems, on the other hand, use different keys that are not feasibly derivable from one another for encryption and decryption. A person wishing to receive messages generates a pair of corresponding encryption and decryption keys. The encryption key is made public, while the corresponding decryption key is kept secret. Anyone wishing to communicate with the receiver may encrypt a message using the receiver's public key. Only the receiver may decrypt the message, however, since only he has the private key. Perhaps the best-known asymmetric encryption system is the RSA encryption system, named after its originators Rivest, Shamir, and Adleman.
The category of symmetric encryption systems can be further subdivided into those which operate on fixed size blocks of data (block ciphers), and those which operate on arbitrary length streams of data (stream ciphers).
While there are many methods of symmetric key block encryption, most popular methods (for example, DES, CAST, RC5, and Blowfish) are based on Type-2 Feistel Networks. A Type-2 Feistel Network consists of dividing the data to be encrypted into two halves, and then performing some number of rounds, where each round consists of transforming the left half of the data based on the right half of the data, and then transforming the right half based on the modified left half. The two transformations are called subrounds; in the case of RC5, for example, there are two subrounds in each of 16 full rounds. These transformations must be invertible. That is, it must be possible to perform some set of operations during decryption that will reverse the transformations performed during encryption. In a standard Feistel network, some non-invertible function of one half of the data is simply exclusive-OR'd with the other half, as the exclusive OR operation provides invertibility, but any invertible function may be used in the general case.
Feistel Networks are not limited to this case of dividing the data into two equal halves. Alternatively, in a Type-1 Feistel the data is divided into n equal words, where n&gt;2. If these words are labeled A(1) to A(n), then a full round consists of n subrounds, where each subround consists of transforming word A(i) based on the value of word A(i-1) (with A(1) transformed by A(n)).
Similarly, a Type-3 Feistel can be constructed in which the data is divided into n equal words, where n&gt;2, but in which each word is used to transform more than one (possibly all) of the other words. For example, A(1) could be used to transform A(2), A(3), and A(4) in one subround. A full round consists of n such subrounds.
Feistel based ciphers typically add additional invertible transformations before, and/or after, each full round. For example, some ciphers exclusive or the entire data block with subkey data before the first round, to complicate certain attacks. "Subkey" refers to using a different key during different rounds, where the subkey values are derived from an input key.
The distinguishing features of different Feistel based ciphers are determined by the choice of the function used to modify a given data word in each subround. Different functions provide different tradeoffs between speed, data size, and security.
Many ciphers, such as DES and CAST, base their subround functions on a construct called a substitution box, or S-box, which is an array of data elements. In operation, a cipher block data word is used as an index into the S-box, and the value at that location is then used as the output value. The entries in the S-box are carefully chosen to have good properties for resistance to various attacks, including differential and linear analysis. Some desirable properties of S-boxes include that if the input words vary by one bit, on average, half the output bits should change, so that even small changes in the input data rapidly spread to all the output bits. Also, the entries in the S-box should be chosen to have little correlation to the index, to provide good resistance to linear attacks. While S-box based functions may provide excellent security, they tend to be slow in software implementations, especially on processors with small register sets, due to the costs of index calculation, and the corresponding higher use of register resources.
Other ciphers, such as RC5, base their subround functions on bit-wise rotations, in which one data word is used to specify an amount to rotate the target word. Data-dependent rotation provides a very fast subround function, as there are no index calculations and no memory references needed, and all the operations can be kept within the registers. Data-dependent rotations, however, tend to have relatively poor resistance to differential attacks, requiring more rounds to ensure security.
There are also a few ciphers, most notably IDEA and its variants, which use integer multiplication in their round functions. Because of the good diffusion properties of the multiplication operation, the round functions of these ciphers have very good resistance to differential attacks. On the other hand, to achieve this resistance these ciphers implement a multiplication in an algebraic field, which forces them to perform operations modulo some prime number. (Typically, this prime is chosen as 2.sup.16 +1). This modular arithmetic complicates operation of the round function and causes a significant slowdown of the cipher. Also, the complicated round function of these ciphers, and in particular the fact that data words are multiplied by each other, makes it harder to analyze their properties and evaluate their security.
In view of the above, a stronger, more flexible algorithm is needed. One way to make a cipher stronger is to increase the number of rounds of ciphering performed: with each successive transformation, the resulting encryption becomes more difficult to break. Another way to increase the strength is to increase the size of the key. Since the contents of the key remain secret, increasing the size adds another level of difficulty for anyone trying to deduce what transformations may have been performed on the original data, because they are unlikely to guess the random number combination making up the key. Yet another way to increase algorithm strength is to increase the size of the "block" on which the cipher performs its transformations. A block is the unit of original data processed during one ciphering operation. The larger the block size, the more difficult it becomes for an adversary to construct a dictionary of plaintext and matching ciphertext, for a given key, large enough to pose a threat to the security of the algorithm. Further, different keys (i.e., subkeys) can be used for each round, increasing the number of random number combinations that would have to be correctly guessed in order to break the cipher.
It will be appreciated that when a cipher allows varying the number of rounds, the key size, the key values, and the block size at the same time, an incredibly difficult challenge is presented to a person attempting to discover the original data contents from an encrypted result. It will also be appreciated that the computations involved to cipher the data are quite complex, and that while performing more rounds of ciphering increases the strength of the result, it also causes computation time to increase. When data is very sensitive, this time spent in ciphering will be warranted. It may be, however, that less sensitive data does not warrant the added time and expense of many rounds of ciphering. By providing an algorithm where the number of rounds, the key size and values, and the block size are variable, the ultimate choice between the level of security required and the amount of computation time utilized rests with the user. By allowing the number of rounds per stage, key size, and block size to vary, the cipher of the present invention becomes, in effect, scalable in three dimensions.
Existing symmetric key block ciphers may provide for variation in the key size, the block size, and the number of rounds of ciphering, but these ciphers define a single type of round function, and iterate that function repeatedly. Existing ciphers tend to avoid use of data-dependent rotations, because reading the rotation amount from the storage location or register holding the data value is computationally very expensive. Further, use of S-boxes in existing ciphers tends to be inefficient, because subkeys are used as indices to access the S-boxes.
Accordingly, a need exists for an improved and more flexible symmetric block cipher which offers excellent resistance to linear and differential attacks; operates quickly and efficiently while using S-boxes; uses data-dependent rotation in a fast, efficient round function; and supports a variable length key, variable length block, and a variable number of rounds per stage.
The technique of the present invention achieves these objectives by using multiple stages while using the fast operations of table lookup, exclusive OR, addition, subtraction, and data-dependent rotation, thereby minimizing the time required to encrypt and decrypt data. Data-dependent rotation is fast because of a novel manner of locating the data value in a single, predetermined register. Table lookup using S-boxes is made faster because some rounds access the S-boxes without using subkeys. The data-independent sub-keys can be precomputed, further minimizing the time required for encryption and decryption. A minimal amount of computer storage is required for data used in the operation of the cipher.